package priv.pront.code.algorithm_daily.acwing.search;

import java.util.*;
import java.io.*;

/**
 * @Description: https://www.acwing.com/problem/content/847/
 * @Author: pront
 * @Time:2024-06-19 15:30
 */
public class A845_八数码 {

    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String start = bf.readLine().replaceAll(" ", "");
        System.out.println(bfs(start));
    }

    private static int bfs(String start){
        Queue<String> queue = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();
        String end = "12345678x";
        queue.add(start);
        map.put(start, 0);
        int[] dx = {0, -1, 0, 1}, dy = {-1, 0, 1, 0};
        while(!queue.isEmpty()){
            String cur = queue.poll();
            int distance = map.get(cur);
            if(cur.equals(end)) return distance;
            int idx = cur.indexOf("x");
            int x = idx / 3, y = idx % 3;
            for(int i = 0; i < 4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
                char[] arr = cur.toCharArray();
                swap(arr, idx, nx * 3 + ny);
                String s = new String(arr);
                if(map.get(s) == null){
                    map.put(s, distance + 1);
                    queue.add(s);
                }
                swap(arr, idx, nx * 3 + ny);
            }
        }
        return -1;
    }

    private static void swap(char[] arr, int a, int b){
        char temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
